Given a positive integern, break it into the sum ofat leasttwo positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, givenn= 2, return 1 (2 = 1 + 1); givenn= 10, return 36 (10 = 3 + 3 + 4).

Note: You may assume thatnis not less than 2 and not larger than 58.

Credits:
Special thanks to@jianchao.li.fighterfor adding this problem and creating all test cases.

class Solution {

public:

int integerBreak\(int n\) {

    int product=1;

    if\(n==2\) return 1;

    if \(n==3\) return 2;

     if \(n==4\) return 4;

    while\(n>4\){

        product\*=3;

        n-=3;

    }



    product\*=n;

    return product;

}

};

这个是参考一个LeetCode的discussion得到的。然后解释是这个，不过我觉得不严密。

For convenience, saynis sufficiently large and can be broken into any smaller real positive numbers. We now try to calculate which real number generates the largest product.
Assume we breakninto(n / x)x's, then the product will bexn/x, and we want to maximize it.

Taking its derivative gives usn * xn/x-2* (1 - ln(x)).
The derivative is positive when0 < x < e, and equal to0whenx = e, then becomes negative whenx > e,
which indicates that the product increases asxincreases, then reaches its maximum whenx = e, then starts dropping.

This reveals the fact that ifnis sufficiently large and we are allowed to breakninto real numbers,
the best idea is to break it into nearly alle's.
On the other hand, ifnis sufficiently large and we can only breakninto integers, we should choose integers that are closer toe.
The only potential candidates are2and3since2 < e < 3, but we will generally prefer3to2. Why?

Of course, one can prove it based on the formula above, but there is a more natural way shown as follows.

6 = 2 + 2 + 2 = 3 + 3. But2 * 2 * 2 < 3 * 3.
Therefore, if there are three2's in the decomposition, we can replace them by two3's to gain a larger product.

All the analysis above assumesnis significantly large. Whennis small (sayn <= 10), it may contain flaws.
For instance, whenn = 4, we have2 * 2 > 3 * 1.
To fix it, we keep breakingninto3's untilngets smaller than10, then solve the problem by brute-force.